﻿namespace h108
{
    public class Solution
    {
        public ListNode DeleteDuplicates(ListNode head) {
            // 1.base cases
            if (head == null || head.next == null) return head;

            // 2.哑节点,快慢指针
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            ListNode slow = dummy;
            ListNode fast = head;

            // 3.1 fast 遍历链表,让fast 去嗅探不相等元素
            // 3.2 slow.next == fast --> slow 与 fast 之间存在重复元素，slow 动。
            // 3.3 slow.next != fast --> slow 与 fast 之间没有重复元素，让slow指向的元素跳过这些重复元素，slow 不动。
            while (fast != null)
            {
                if (fast.val != fast.next?.val)
                {                  
                    if (slow.next == fast)     //   3.2 & 3.3 
                    {
                        slow = fast;
                    }
                    else                    
                    {
                        slow.next = fast.next;
                    }
                }
                fast = fast.next;
            }

            return dummy.next;
        }

    }
}